package dp;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class RegularExpressionMatching10 {

    @Test
    public void test() {
        isMatch("aa", "a");
        isMatch("aa", "a*");
        isMatch("ab", ".*");
        isMatch("aab", "c*a*b");
        isMatch("mississippi", "mis*is*p*.");
    }

    public boolean isMatch(String s, String pattern) {
        List<MyChar> t = MyChar.split(pattern);
        // 为方便计算, 在两者前面引入虚拟的头部空字符, 只能与带'*'的匹配
        // 以pattern为第一维度, string为第二维度
        boolean[][] dp = new boolean[t.size()+1][s.length()+1];

        // 头部空字符相匹配
        dp[0][0] = true;

        for (int i = 1; i <= t.size(); i++) {
            // 带"*"的前缀与空字符相匹配
            dp[i][0] = dp[i-1][0] &&
                    t.get(i-1).isStar; // 这一个是"*"
            if (i >= 2) {
                dp[i][0] = dp[i][0] && t.get(i-2).isStar; // 上一个是"*"
            }
        }

        // 空字符 与 任意字符 不匹配
        for (int j = 1; j <= s.length() ; j++) {
            dp[0][j] = false;
        }

        for (int i = 1; i <= t.size() ; i++) {
            for (int j = 1; j <= s.length(); j++) {
                dp[i][j] = false;
                MyChar p = t.get(i-1);
                char c = s.charAt(j-1);

                // if分支以前面的dp为区分条件, 不要以c[i]==s[j]为分区条件

                // ac 与 ac
                // a. 与 ac
                if (dp[i-1][j-1] && p.matchChar(c)) {
                    dp[i][j] = true;
                    continue;
                }

                // a*c* 与 aaa
                if (dp[i-1][j] && p.isStar) {
                    dp[i][j] = true;
                    continue;
                }

                // ac* 与 acc
                if (dp[i][j-1] && p.isStar && p.matchChar(c)) {
                    dp[i][j] = true;
                    continue;
                }
            }
        }
        System.out.format("p: %s, s: %s, match: %s\n", pattern, s, dp[t.size()][s.length()]);
        return dp[t.size()][s.length()];
    }

    static class MyChar {
        char ch;
        boolean isStar;

        public boolean matchChar(char ch1) {
            return ch == '.' || ch == ch1;
        }

        public static List<MyChar> split(String p) {
            List<MyChar> list = new ArrayList<>(p.length());
            int index = 0;
            while (index < p.length()) {
                if (index < p.length()-1 && p.charAt(index+1) == '*') {
                    list.add(new MyChar(p.charAt(index), true));
                    index++;
                } else {
                    list.add(new MyChar(p.charAt(index), false));
                }
                index++;
            }
            return list;
        }

        public MyChar(char ch, boolean isStar) {
            this.ch = ch;
            this.isStar = isStar;
        }
    }
}
